package com.gxc.linkedList;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 19. 删除链表的倒数第 N 个结点
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 * 初始时 first 和 second 均指向头节点。我们首先使用 first 先走 n步骤。
 * 此时，first 和 second 之间间隔了 n−1 个节点，即 first 比 second 超前了 n 个节点。
 */
public class RemoveNthFromEnd {

    public static void main(String[] args) {
        test();
    }

    public static void test() {
        ListNode head = new ListNode(3);

        ListNode node1 = new ListNode(7);
        ListNode node2 = new ListNode(9);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(8);
        ListNode node6 = new ListNode(0);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;

        print(head);
        System.out.println("---------");
        ListNode node = handle(head, 1);
        print(node);
    }

    //递归 递归是栈
    public static ListNode handle(ListNode head, int n) {
        int last = recursion(head, n, 1);
        //删除倒数第n个节点 是第一个节点
        if (last == n) {
            head = head.next;
        }
        return head;
    }

    public static int recursion(ListNode node, int n, int i) {
        if (node.next == null) {
            return i;
        }
        int last = recursion(node.next, n, i+1);

        if (last-n == i) {
            if (node.next!=null) {
                node.next = node.next.next;
            }
        }
        return last;
    }

  public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

    private static void print(ListNode head) {
        while (head!=null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    //双循环  栈 根据栈「先进后出」的原则，我们弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(0, head);
            Deque<ListNode> stack = new LinkedList<ListNode>();
            ListNode cur = dummy;
            while (cur != null) {
                stack.push(cur);
                cur = cur.next;
            }
            for (int i = 0; i < n; ++i) {
                stack.pop();
            }
            ListNode prev = stack.peek();
            prev.next = prev.next.next;
            ListNode ans = dummy.next;
            return ans;
        }
    }

    //双指针
    // 可以使用两个指针 first 和 second 同时对链表进行遍历，
    // 并且 first 比 second 超前 n 个节点。当 first 遍历到链表的末尾时，
    // second 就恰好处于倒数第 n 个节点。
    //
    //具体地，初始时 first 和 second 均指向头节点。
    // 我们首先使用 first 对链表进行遍历，遍历的次数为 n。
    // 此时，first 和 second 之间间隔了 n−1 个节点，
    // 即 first 比 second 超前了 n 个节点。
    //
    //在这之后，我们同时使用 first 和 second 对链表进行遍历。
    // 当 first 遍历到链表的末尾（即 first 为空指针）时，
    // second 恰好指向倒数第 n 个节点。
    /**
     * 双指针  初始间隔
     */
    class Solution2 {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(0, head);
            ListNode first = head;
            ListNode second = dummy;
            for (int i = 0; i < n; ++i) {
                first = first.next;
            }
            while (first != null) {
                first = first.next;
                second = second.next;
            }
            second.next = second.next.next;
            ListNode ans = dummy.next;
            return ans;
        }
    }

}
